This invention concerns data compression, and relates particularly, but not exclusively, to apparatus for compressing digital data derived from coloured pictures, especially maps.
It is usual to seek to store as much data as possible in the smallest space. This is especially true as regards pictures, particularly maps, when they are to be stored in digital form in association with some computerised retrieval and display system.
For various reasons it may be desirable to digitise a picture, such as a map of some area, by sampling what it shows in very small adjacent regularly spaced areas, or pixels, and converting what is seen in the sampled area into a number representing that area. The resultant stream of digits is then stored in some suitable way, for example as magnetic pulses on computer tape, disk or bubble, or as electrical charges in a computer semiconductor memory. This technique may be termed `simple digitization. ` At some later date the stored digital data may be retrieved and used to reconstitute the original picture, perhaps by controlling a colour plotter/pointer or a co-our television display to show the picture. All of this is technically possible. The digitisation, storage, retrieval and display of map data is desirable in several fields. For example, in a moving vehicle, such as a car or an aeroplane, it is very convenient to have a display of the area through or over which the vehicle is passing. This allows the driver or pilot to see exactly where he is without needing to keep, and follow his progress over, a series of maps relating to the areas where he is likely to go. When a comuter is used to generate and control the display it is relatively easy to link the vehicle's movement with the map, so that the vehicle's position can be seen at a glance. However, there is a particular problem with map data, in that the data takes up a very large area of storage space. This presents difficulties both in storing and in rapidly retrieving and displaying any chosen area of map.
Various techniques for compressing pictorial data have been proposed. By compression of pictorial data it is meant that the picture is converted into a set of numbers taking up less storage space than is required for a simple digitisation. An indication of the degree of compression is given by the ratio of the simple digitisation size to the compressed data size and this is termed the compression factor. However the compression factors available with previous techniques are not always satisfactory. For example, one classic compression method is that referred to as "runlength" coding. Any map-like picture has parts that are the same over a large area. A strip or run of such a part can be stored, in coded form, as the length of the run, i.e. a number of small areas all of this one kind such as say, "15 blue" or "27 white". This takes up less room than storing each area separately. However, runlength coding can rarely give a compression factor much greater than about 5, but naturally this depends on the map and the frequency of features it depicts. Although this is useful nevertheless higher compression factors are very desirable.